home *** CD-ROM | disk | FTP | other *** search
/ Chip 2004 October / Chip_2004-10_cd1.bin / program / ctenari / Jaros / rozvrhy_install.exe / {app} / readme.txt < prev    next >
Text File  |  2004-08-23  |  11KB  |  268 lines
  1. +----------------------------------------------------+
  2. |     TV∙RCE ROZVRH┘ 2.3 (c) PAVEL JAROè 2003-04     |
  3. +----------------------------------------------------+
  4. |    Autor:    PAVEL JAROè / FUNKYSHiT               |
  5. |    Web:      http://funkyshit.webpark.cz/          |
  6. |    E-mail:   jaros.pavel@centrum.cz                |
  7. +----------------------------------------------------+
  8.  
  9. +----------------------------------------------------+
  10. | OBSAH                                              |
  11. +----------------------------------------------------+
  12.   
  13.   I.   Nßroky na HW a SW
  14.   II.  Instalace
  15.   III. Co je Tv∙rce rozvrh∙
  16.   IV.  Ovlßdßnφ programu
  17.        1) Zadßnφ vstupnφch dat
  18.        2) Ulo₧enφ vstupnφch dat
  19.        3) Ovlßdßnφ genetickΘho algoritmu
  20.        4) Ulo₧enφ v²stupnφch dat
  21.        5) Popis parametr∙ GA        
  22.   V.   Odpov∞dnost za vady
  23.  
  24. +----------------------------------------------------+
  25. | I. N┴ROKY NA HW A SW                               |
  26. +----------------------------------------------------+
  27.  
  28.   SystΘm s WIN95 a vyÜÜφ.
  29.  
  30. +----------------------------------------------------+
  31. | II. INSTALACE                                      |
  32. +----------------------------------------------------+
  33.   
  34.   Spus¥te instalaΦnφ soubor a postupujte podle in-
  35.   strukcφ instalaΦnφho programu.
  36.  
  37. +----------------------------------------------------+
  38. | III. CO JE TV┘RCE ROZVRH┘                          |
  39. +----------------------------------------------------+
  40.  
  41.   Program Tv∙rce rozvrh∙ umo₧≥uje pln∞ automatickou 
  42.   tvorbu Ükolnφch rozvrh∙ s vyu₧itφm techniky gene-
  43.   tick²ch algoritm∙.
  44.  
  45.   Program sestavuje Ükolnφ rozvrhy podle zadan²ch 
  46.   omezujφcφch podmφnek, kter²mi jsou: 
  47.  
  48.     1) Silnß omezenφ (povinnß)
  49.        -----------------------  
  50.        - pouze jedinΘ: ₧ßdn² uΦitel nesmφ uΦit 
  51.          v danΘm Φase vφce ne₧ jeden p°edm∞t.
  52.  
  53.   Je nutnΘ, aby v p°φpustnΘm °eÜenφ rozvrhovacφ ·lohy
  54.   nebyl ₧ßdn² t∞₧k² konflikt, tzn. aby vygenerovanΘ
  55.   rozvrhy spl≥ovaly silnß omezenφ.        
  56.  
  57.     2) Slabß omezenφ (volitelnß)
  58.        -------------------------
  59.        - maximßlnφ p°φpustnß mezera v rozvrhu,
  60.        - maximßlnφ p°φpustn² poΦet hodin denn∞,
  61.        - minimßlnφ p°φpustn² poΦet hodin denn∞.
  62.   
  63.   Napln∞nφ vÜech slab²ch omezenφ nenφ pro p°φpustnΘ 
  64.   °eÜenφ nezbytn∞ nutnΘ, p°esto p°i tvorb∞ rozvrh∙
  65.   hrajφ d∙le₧itou roli. Prßv∞ slabß omezenφ urΦujφ
  66.   do jakΘ mφry budou vygenerovanΘ rozvrhy pou₧itelnΘ
  67.   v praxi. V Φφm v∞tÜφ mφ°e jsou omezujφcφ podmφnky
  68.   (silnΘ i slabΘ) spln∞ny, tφm je °eÜenφ kvalitn∞jÜφ.
  69.  
  70.   Program Tv∙rce rozvrh∙ pou₧φvß pro nalezenφ opti-
  71.   mßlnφho °eÜenφ techniku genetick²ch algoritm∙ (GA), 
  72.   kterß je zalo₧ena na p°irozenΘm v²b∞ru, repro-
  73.   dukΦnφm procesu a mutaci genetickΘ informace.
  74.   GA pracuje s populacφ jedinc∙, kterß se vyvφjφ 
  75.   v Φase. Ka₧d² jedinec v populaci odpovφdß jednomu
  76.   z mo₧n²ch °eÜenφ ·lohy (rozvrh∙). V pr∙b∞hu gene-
  77.   racφ (Φasu) dochßzφ k nßr∙stu kvality populace 
  78.   jedinc∙. Toho je dosa₧eno dosa₧eno aplikovßnφm 
  79.   selekce, k°φ₧enφ a mutace. Selekce provßdφ v²b∞r
  80.   jedinc∙, kte°φ se podφlφ na reprodukci. ╚φm je je-
  81.   dinec kvalitn∞jÜφ, tφm v∞tÜφ mß Üanci, ₧e bude vy-
  82.   brßn. K°φ₧enφ zajiÜ¥uje v²m∞nu genetickΘho materiß-
  83.   lu mezi dv∞ma jedinci - rodiΦi. Potomek zφskß od 
  84.   ka₧dΘho rodiΦe pouze Φßst genetickΘ inforamce. A 
  85.   koneΦn∞ mutace udr₧uje variabilitu v populaci, aby
  86.   proces hledßnφ °eÜenφ neuvφzl v lokßlnφm optimu.   
  87.   Program Tv∙rce rozvrh∙ navφc pou₧φvß tvz. opravnou
  88.   mutaci, kterß v²znamn∞ napomßhß p°i odstra≥ovßnφ
  89.   konflikt∙ v rozvrhu. Vφce inforamcφ o genetick²ch 
  90.   algoritmech m∙₧ete najφt nap°. na:
  91.   http://alife.fei.tuke.sk/projekty/gen_alg/. 
  92.  
  93.   V²stupem programu jsou jednak rozvrhy hodin pro
  94.   jednotlivΘ t°φdy, jednak rozvrhy uΦitel∙.  
  95.  
  96. +----------------------------------------------------+
  97. | IV. OVL┴D┴N═ PROGRAMU                              |
  98. +----------------------------------------------------+
  99.  
  100.   1) Zadßnφ vstupnφch dat
  101.      --------------------
  102.  
  103.   Prvnφm krokem je zadßnφ vstupnφch dat. To je mo₧nΘ
  104.   provΘst bu∩ s pomocφ pr∙vodce nebo ·pravou ji₧ 
  105.   existujφcφch dat.
  106.  
  107.   Pr∙vodce pro zadßvßnφ dat m∙₧ete spustit bu∩ z na-
  108.   bφdky Soubor p°φkazem Zadat data... nebo tlaΦφtkem 
  109.   s ikonou rozvrhu na panelu nßstroj∙ (CTRL+Z).
  110.  
  111.   Nejprve budete vyzvßni k zadßnφ jmΘna souboru se
  112.   vstupnφmi daty (takΘ m∙₧ete p°epsat ji₧ existujφcφ 
  113.   soubor). DalÜφm krokem je napln∞nφ seznamu vyuΦujφ-
  114.   cφch. Na nßsledujφcφm formulß°i zadßte p°edm∞ty
  115.   pro jednotlivΘ t°φdy. U ka₧dΘho p°edm∞tu je t°eba
  116.   vyplnit jeho nßzev, poΦet hodin a zvolit vyuΦujφcφ-
  117.   ho ze seznamu vyuΦujφcφch. Na tomto formulß°i je
  118.   takΘ mo₧nΘ zadat p°edm∞ty s pevn∞ stanov²m dnem
  119.   a hodinou v²uky. Na prvnφ zßlo₧ce poslednφho for-
  120.   mulß°e pr∙vodce nastavφte chovßnφ genetickΘho algo-
  121.   ritmu (poΦet generacφ, poΦet jedinc∙ v generaci, 
  122.   pravd∞podobnosti k°φ₧enφ a mutace atd. - viz 
  123.   Popis parametr∙ GA) a na druhΘ zßlo₧ce zadßte
  124.   data t²kajφcφ se rozvrhu (poΦet hodin denn∞, poΦet
  125.   dn∙ v t²dnu, omezujφcφ podmφnky).
  126.  
  127.   DalÜφ mo₧nostφ je ·prava ji₧ existujφcφch dat.
  128.   Ke vstupnφm dat∙m lze p°istupovat p°es nabφdku Data.
  129.   Formulß° s nastavenφm genetickΘho algoritmu zobra-
  130.   zφte p°φkazem Nastavenφ GA... z nabφdky GA 
  131.   (klßvesovΘ zkratky F5 - F8).
  132.  
  133.  
  134.   2) Ulo₧enφ vstupnφch dat
  135.      ---------------------
  136.   
  137.   Vstupnφ data je mo₧nΘ uklßdat (CTRL+U) a naΦφtat 
  138.   (CTRL+N). K tomu slou₧φ bu∩ p°φkazy v nabφdce soubor 
  139.   nebo tlaΦφtka na panelu nßstroj∙. Vstupnφ data je 
  140.   mo₧nΘ uklßdat ve dvou r∙zn²ch formßtech:
  141.  
  142.    a) Formßt DAT - data v tomto souboru, nelze upra-
  143.       vovat pomocφ textovΘho editoru (jako je nap°. 
  144.       Poznßmkov² blok - Notepad). Zm∞ny je mo₧nΘ pro-
  145.       vßd∞t pouze v programu Tv∙rce rozvrh∙. V²hodou
  146.       tohoto formßtu je vysokß rychlost p°i uklßdßnφ
  147.       a naΦφtßnφ vstupnφch dat.
  148.  
  149.    b) Formßt INI - data lze m∞nit jak v programu, tak
  150.       pomocφ textovΘho editoru, ovÜem za cenu pomalej-
  151.       Üφho uklßdßnφ a naΦφtßnφ (co₧ se projevφ zvlßÜt∞
  152.       pokud soubor obsahuje velkΘ mno₧stvφ dat).
  153.  
  154.   Mezi t∞mito formßty je mo₧nΘ provßd∞t konverze, tzn. 
  155.   naΦφst vstupnφ data ve formßtu DAT a ulo₧it je do sou-
  156.   boru typu INI nebo naopak.
  157.  
  158.  
  159.   3) Ovlßdßnφ genetickΘho algoritmu
  160.      ------------------------------
  161.   
  162.   Pokud mß program k dispozici vÜechna pot°ebnß 
  163.   vstupnφ data je mo₧nΘ zahßjit genetick² algoritmus.
  164.   K ovlßdßnφ genetickΘho algoritmu je mo₧nΘ pou₧φt
  165.   bu∩ p°φkazy v nabφdce GA nebo tlaΦφtka Start/Pauza/
  166.   Stop na panelu nßstroj∙ (klßvesovΘ zkratky F2 - F4).
  167.  
  168.   Genetick² algoritmus zahßjφte p°φkazem Start, jeho
  169.   b∞h m∙₧ete kdykoliv p°eruÜit p°φkazem Pauza a nechat
  170.   si vypsat dosud nejlepÜφ nalezenΘ °eÜenφ. ╚innost
  171.   algoritmu lze potΘ znovu obnovit p°φkazem Start.
  172.   Algoritmus ukonΦφte p°φkazem Stop.
  173.  
  174.   Pokud je nalezeno °eÜenφ, kterΘ spl≥uje vÜechny
  175.   omezujφcφ podmφnky, je genetick² algoritmus ukonΦen
  176.   automaticky.  
  177.   
  178.   4) Ulo₧enφ v²stupnφch dat
  179.      ----------------------
  180.   
  181.   NalezenΘ °eÜenφ je mo₧nΘ ulo₧it (CTRL+S) do texto-
  182.   vΘho souboru a odtud znovu naΦφst (CTRl+R).
  183.   V²stupnφ data se uklßdajφ jako text odd∞len² st°ed-
  184.   nφky, co₧ je formßt vhodn² pro dalÜφ zpracovßnφ v 
  185.   tabulkovΘm procesoru (nap°. MS Excel).
  186.  
  187.   5) Popis parametr∙ GA
  188.      ------------------
  189.   Pro efektivnφ Φinnost GA je klφΦovΘ jeho sprßvnΘ 
  190.   nastavenφ. Uvßdφm struΦn² popis jednotliv²ch para-
  191.   metr∙ GA, kter² by vßm to m∞l pokud mo₧no usnadnit.
  192.  
  193.   a) P°eruÜit p°i stagnaci trvajφcφ po XX generacφ 
  194.      - v p°φpad∞, ₧e nebylo po urΦit² poΦet generacφ
  195.      nalezeno ₧ßdnΘ kvalitn∞jÜφ °eÜenφ, dojde k auto-
  196.      matickΘmu p°eruÜenφ GA. V p°φpad∞, ₧e proces 
  197.      hledßnφ °eÜenφ nikam nevede, je ukonΦeno a zahßjφ
  198.      se novΘ hledßnφ (viz parametr PoΦet nezßvisl²ch 
  199.      b∞h∙ GA). Pokud je parametr nastaven na 0, k p°e-
  200.      ruÜenφ nedojde a b∞h GA je ukonΦen po nastavenΘm
  201.      poΦtu generacφ. 
  202.  
  203.   b) PoΦet nezßvisl²ch b∞h∙ GA - urΦuje poΦet opakovßnφ
  204.      GA. ╪eÜenφm ulohy pak bude nejkvalitn∞jÜφ nalezen²
  205.      rozvrh ze vÜech b∞h∙. Pokud je v n∞kterΘm b∞hu na-
  206.      lezeno °eÜenφ bez konflikt∙, dojde k p°eruÜenφ GA 
  207.      a zb²vajφcφ b∞hy se ji₧ neprovedou.
  208.  
  209.   c) PoΦet generacφ - urΦuje poΦet iteracφ GA. 
  210.      V p°φpad∞, ₧e mßte nasataveno p°eruÜenφ p°i 
  211.      stagnaci, m∙₧e dojφt k ukonΦenφ b∞hu GA p°ed
  212.      dosa₧enφm zvolenΘho poΦtu generacφ. TakΘ v p°φ-
  213.      pad∞, ₧e je nalezeno °eÜenφ bez konflikt∙, dojde
  214.      k p°eruÜenφ GA. DoporuΦuji nastavit vyÜÜφ poΦet
  215.      generacφ (200 a vφce) a souΦasn∞ zapnout p°eru-
  216.      Üenφ p°i stagnaci. 
  217.  
  218.   d) PoΦet jedinc∙ - urΦuje poΦet jedinc∙ v populaci. 
  219.      ╚φm vyÜÜφ poΦet jedinc∙ nastavφte, tφm ÜφrÜφ 
  220.      prostor (mo₧n²ch °eÜenφ) je prohledßvßn a tφm 
  221.      vyÜÜφ je pravd∞pobnost nalezenφ optimßlnφho 
  222.      °eÜenφ. Um∞rn∞ tomu se vÜak sni₧uje i rychlost
  223.      programu. Dobr²ch v²sledk∙ lze dosßhnout zhruba 
  224.      ji₧ od 100 jedinc∙.
  225.  
  226.   e) PoΦet elitnφch jedinc∙ - urΦuje poΦet nejkvalit-
  227.      n∞jÜφch jedinc∙, kte°φ automaticky postupujφ do 
  228.      dalÜφ generace (beze zm∞n), ani₧ by proÜli se-
  229.      lekcφ, k°φ₧enφm a mutacφ. 
  230.      Standardn∞: 1 - 5 jedinc∙.
  231.  
  232.   f) Pravd∞podobnost k°φ₧enφ - urΦuje s jakou pravd∞-
  233.      pobnostφ mß dochßzet ke k°φ₧enφ. 
  234.      Stanadardn∞: 50 - 75 %.
  235.  
  236.   g) Hornφ a dolnφ pravd∞podobnost "opravnΘ" mutace - 
  237.      v p°φpad∞ ·plnΘho GA je opravnß mutace aplikovßna
  238.      dynamicky: z poΦßtku s vyÜÜφ pravd∞pobnostφ, poz-
  239.      d∞ji s ni₧Üφ. To lze interpretovat tak, ₧e v poΦß-
  240.      teΦnφch generacφch je preferovßna v∞tÜφ Üφ°e pro-
  241.      hledßvanΘho prostoru (mo₧n²ch °eÜenφ) a v pozd∞j-
  242.      Üφch generacφch jsou spφÜe prohledßvßna blφzkß 
  243.      okolφ nejkvalitn∞jÜφch °eÜenφ. 
  244.      Stanadardn∞: 100 % a 25 %.
  245.  
  246.   h) Pravd∞podobnost mutace - pevn∞ definovanΘ p°edm∞ty 
  247.      - stanovuje s jakou pravd∞podobnostφ mß dochßzet k
  248.      opravnΘ mutaci na dnech v rozvrhu, ve kter²ch jsou
  249.      pevn∞ definovanΘ p°edm∞ty (s pevn∞ stanovenou do-
  250.      bou v²uky). Stanadardn∞: 50 - 75 %.
  251.  
  252.  
  253.   i) Pravd∞podobnost "klasickΘ" mutace - urΦuje s ja-
  254.      kou pravd∞pobnostφ mß dochßzet ke klasickΘ mutaci. 
  255.      Stanadardn∞: 1 - 5 %.
  256.  
  257.  
  258. +----------------------------------------------------+
  259. | V. ODPOV╠DNOST ZA VADY                             |
  260. +----------------------------------------------------+
  261.  
  262.   Autor nenφ zodpov∞dn² za ztrßtu nebo zniΦenφ dat, 
  263.   uÜl² zisk nebo jak²koliv jin² druh ztrßty spojen² 
  264.   s u₧φvßnφm tohoto programu.
  265.  
  266. +----------------------------------------------------+
  267. |                           Pavel JaroÜ, 21. 8. 2004 |
  268. +----------------------------------------------------+